package A_review.review11_08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main39 {

       ArrayList<Integer> path=new ArrayList<Integer>();
       List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
           backtracking(candidates,target,0,0);
        return  ans;
    }

    public  void  backtracking(int[] cadidates,int target,int sum,int start){
        if (sum>target){
            return;
        }
        if (sum==target){
            ans.add(new ArrayList<>(path));
            return;
        }
        //TODO:2023/11/8  这里是关键
        for (int i = start; i < cadidates.length ; i++) {
            sum+=cadidates[i];
               path.add(cadidates[i]);
               backtracking(cadidates, target, sum,i);
               sum-=cadidates[i];
               path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        Main39 main39 = new Main39();
        int[] arr={2,3,6,7};
        List<List<Integer>> list = main39.combinationSum(arr, 7);
        for (List a:list
             ) {
            System.out.println(a.toString());
            System.out.println("====================");
        }
    }
}
